#include "bigint.h"
#include <iostream>
#include <string>
#include <cstdlib>
using namespace std;

const int BASE = 10000;

BigInt::BigInt()
{
	virSize = 4;
	realSize = 0;
	digArray = new int [virSize];
}
BigInt::BigInt(BigInt& bigNum)
{
	if(this == &bigNum) return;
	realSize = bigNum.realSize;
	virSize = bigNum.virSize;
	digArray = new int[virSize];
	for(size_t i = 0; i < virSize; ++i)
	{
		digArray[i] = bigNum[i];
	}
}
BigInt:: ~BigInt()
{
	delete [] digArray;
	virSize = 0 ;
	realSize = 0;
}
int& BigInt::operator [](size_t x)
{
	return digArray[x];
}
BigInt& BigInt::operator =(BigInt& bigNum)
{
	if(this == &bigNum) return bigNum;
	realSize = bigNum.realSize;
	virSize = bigNum.virSize;
	delete [] digArray;
	digArray = new int[virSize];
	for(size_t i = 0; i < virSize; ++i)
	{
		digArray[i] = bigNum[i];
	}
	return *this;
}
void BigInt::Clear()
{
	delete [] digArray;
	realSize = 0;
	virSize = 4;
	digArray = new int [virSize];
}
void BigInt::Push(int num)
{
	if(realSize == virSize)
	{
		virSize *= 2;
		digArray = (int*)realloc(digArray, virSize);
	}
	digArray[ realSize++ ] = num;
}
int BigInt::Pop()
{
	int ans = digArray[realSize - 1];
	--realSize;
	if(realSize * 2 < virSize && virSize > 4) 
	{
		virSize /= 2;
		digArray = (int*)realloc(digArray, virSize);
	}
	return ans;
}
int CharToInt( char c)
{
	if(c >= '0' && c <= '9')
	{
		return c - '0';
	}
	return 10000;
}
string IntToStr(int x)
{
	string ans = "";
	int dig = BASE / 10;
	while(x || dig)
	{
		if( x / dig != 0)
		{
			ans += x / dig + '0';
		}
		else
			ans +="0";
		x = x - ((x / dig) * dig);
		dig /= 10;
	}
	if(ans=="") return "0000";
	return ans;
}
void StrToBigInt(string s, BigInt& num)
{
	int tmp = 0;
	int dig = 1;
	size_t i = s.size();
	for( i = i - 1; ; --i)
	{
		tmp += CharToInt(s[i]) * dig;
		if(tmp > BASE && dig != BASE) { return; }
		dig *= 10;
		if(dig == BASE)
		{
			num.Push(tmp);
			tmp = 0;
			dig = 1;
		}
		if( i == 0 ) break;
	}
	if(tmp != 0)
	{
		num.Push(tmp);
	}
	return;
}
string BigIntToStr(BigInt& num)
{
	string s;
	for(size_t i = num.realSize - 1; i>=0; --i)
	{
		s += IntToStr(num[i]);
		if(i == num.realSize -1 ) 
		{
			string tr = "";
			bool f = false;
			for(size_t i = 0; i < 4; ++i)
			{
				if(s[i] == '0' && !f) continue;
				f = true;
				tr += s[i];
			}
			s = tr;
		}
		if( i == 0) break;
	}
	return s;
}
void Sum(BigInt& bigNumA, BigInt& bigNumB, BigInt& ans)
{
	int p = 0;
	ans.Clear();
	for(size_t i = 0 ; i < max(bigNumA.realSize, bigNumB.realSize); ++i)
	{
		if(bigNumA.realSize > i)
		{
			p += bigNumA[i];
		}
		if(bigNumB.realSize > i)
		{
			p += bigNumB[i];
		}
		ans.Push(p % BASE);
		p /= BASE;
	}
}
void Sub(BigInt& bigNumA, BigInt& bigNumB, BigInt& ans)
{
	int p = 0;
	size_t i = 0;
	ans.Clear();
	ans = bigNumA;
	for(i = 0; i < bigNumB.realSize; ++i)
	{
		if(ans[i] - bigNumB[i] - p < 0) 
		{
			ans[i] += BASE;
			ans[i] -= (bigNumB[i] + p);
			p = 1;
		}
		else
		{
			ans[i] -= (bigNumB[i] + p);
			p = 0;
		}
		
	}
	while(p)
	{
		if(ans[i] - p < 0) 
		{
			ans[i] += BASE;
			ans[i] -= p;
			p = 1;
		}
		else
		{
			ans[i] -= p;
			p = 0;
		}
		++i;
	}
	while(!ans[ans.realSize - 1] && ans.realSize!=0)
	{
		ans.Pop();
	}
	return;
}
/*
void Mul(BigInt& bigNumA, BigInt& bigNumB, BigInt& ans)
{
	if(bigNumA.size == 1 || bigNumB == 1)
	{
		
	}
}
//*/